package com.platform.modules.alg.alglib.poj3264;

public class Poj3264 {
    public String output = "";
    private final int maxn = 50010;
    int h[] = new int[maxn];
    // F(i,j) 表示区间[i，i+2^j-1]的最值，区间长度为 2^j
    private int Fmax[][] = new int[maxn][20];
    private int Fmin[][] = new int[maxn][20];
    private int N;
    private int Q;

    void ST_create() {
        for (int i = 1; i <= N; i++)//初始化
            Fmax[i][0] = Fmin[i][0] = h[i];
        int k = (int) Math.floor(Math.log(N) / Math.log(2));
        for (int j = 1; j <= k; j++)
            for (int i = 1; i <= N - (1 << j) + 1; i++)//N-2^j+1
            {
                Fmax[i][j] = Math.max(Fmax[i][j - 1], Fmax[i + (1 << (j - 1))][j - 1]);
                Fmin[i][j] = Math.min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);
            }
    }

    // 求区间 [l..r] 的最值差
    int RMQ(int l, int r) {
        int k = (int) Math.floor(Math.log(r - l + 1) / Math.log(2));
        int m1 = Math.max(Fmax[l][k], Fmax[r - (1 << k) + 1][k]);
        int m2 = Math.min(Fmin[l][k], Fmin[r - (1 << k) + 1][k]);
        return m1 - m2; // 取两个区间最值差
    }

    public String cal(String input) {
        int a, b;
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        N = Integer.parseInt(words[0]);
        Q = Integer.parseInt(words[1]);

        for (int i = 1; i <= N; i++) // 下标从 1 开始
            h[i] = Integer.parseInt(line[i]);
        ST_create();
        for (int j = 1; j <= Q; j++) {
            String[] nums = line[j + N].split(" ");
            a = Integer.parseInt(nums[0]);
            b = Integer.parseInt(nums[1]);
            output += RMQ(a, b) + "\n";
        }

        return output;
    }
}
